package com.wtgroup.demo.leetcode.q354_俄罗斯套娃信封问题;

import com.wtgroup.demo.common.util.InputParseUtil;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * @author 60906
 * @date 2021/5/11 15:25
 */
public class Q354 {

    @Test
    public void foo1() {
        List input = InputParseUtil.parse("[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]");
        int[][] envelopes = InputParseUtil.listToArray2Int(input);
        int res = new Solution_TryGreed().maxEnvelopes(envelopes);
        System.out.println(res);
    }


    /*尝试贪心 => 贪心无效.
    左端点表示宽度, 右端点表示高度.
    <pre>
             ┌───┐
             └───┘
         ┌───────────────────────┐
         └───────────────────────┘
        ┌───────────┐
        └───────────┘
      ┌─────────────────┐
      └─────────────────┘
     </pre>
     贪心会选择 第1个和第2个, 得到2, 实际应该选择第1个, 第3个, 第4个, 得到4个.
     */
    class Solution_TryGreed {
        public int maxEnvelopes(int[][] envelopes) {
            if (envelopes == null || envelopes.length == 0) {
                return 0;
            }
            Arrays.sort(envelopes, (a, b) -> {
                int k = a[0] - b[0];
                return k == 0 ? a[1] - b[1] : k;
            });
            int ans = 1;
            int[] tempMaxEnvelop = envelopes[0];
            for (int i = 1; i < envelopes.length; i++) {
                int[] currEnvelop = envelopes[i];
                if (currEnvelop[0] > tempMaxEnvelop[0] && currEnvelop[1] > tempMaxEnvelop[1]) {
                    tempMaxEnvelop = currEnvelop;
                    ans++;
                }
            }

            return ans;
        }
    }


    /**
     * 1. 排序
     * 2. 最长子序列解.
     * 控制宽度的前提下, 高度最长子序列, 必然能套起来, 且是最多的.
     * 技巧: 宽度相同的怎么处理? 宽度相同实际没法套的.
     */
    class Solution_LC {

        public int maxEnvelopes(int[][] envelopes) {
            if (envelopes == null || envelopes.length == 0) {
                return 0;
            }
            Arrays.sort(envelopes, (a, b) -> {
                int t = a[0] - b[0];
                if (t == 0) {
                    return b[1] - a[1];
                }
                return t;
            });

            return longestSeqOfHeight(envelopes);
        }

        // 求高度的最长子序列
        private int longestSeqOfHeight(int[][] envelopes) {
            int N = envelopes.length;
            int[] dp = new int[N];
            int ans = 1;
            for (int i = 0; i < N; i++) {
                dp[i] = 1; // 肯定至少为1
                for (int j = 0; j < i; j++) {
                    if (envelopes[j][1] < envelopes[i][1]) {
                        dp[i] = Math.max(dp[j] + 1, dp[i]);
                    }
                }
                ans = Math.max(ans, dp[i]);
            }

            return ans;
        }

    }


}
